package q513_findBottomLeftValue;

import CommonClass.Common.TreeNode;
public class Solution_2 {
    int maxLevel = -1;
    int ans = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    /**
     * 为什么能够保证最后搜索到的是最下面的行中最左侧的节点？
     * 这里需要观察dfs的判断顺序，首先如果遇到一个叶子节点
     * 先观察它所在层数 ： 如果比当前所记录的最大层数小，那么这个叶子节点显然不是结果
     * 还有一种情况 也就是该叶子叶子节点与当前记录的最大层数相等
     * 什么时候会出现这种情况？
     * 根据我们遍历的顺序，中 - 左 - 右
     * 每当我们到达新的一层，都是先从最左侧的节点开始记录并更新最大层数
     * 因此 只有当遇到同一层的非最左侧节点时，才会出现同样的最大层数
     * 这样的方法也就能够保证答案一定记录的是最左侧的节点值
     */
    private void dfs(TreeNode root, int level) {
        // 这里使用的是中序遍历的方式
        // 首先是根
        if (root.left == null && root.right == null) {
            if (level > maxLevel) {
                maxLevel = level;
                ans = root.val;
            }
            return;
        }
        // 然后是左
        if (root.left != null) {
            dfs(root.left, level + 1);
        }
        // 最后是右
        if (root.right != null) {
            dfs(root.right, level + 1);
        }


    }


}
